/**
 * @file src/search/SimulatedAnnealing.java
 */
package search;

/** imports */
import datatypes.ISchedule;
import datatypes.Map3D;
import datatypes.MyTimer;
import datatypes.Point3D;
import java.util.Random;
import java.util.Vector;

/**
 * Simulated Annealing hill climbing blass 
 */
public class SimulatedAnnealing
{
	/**
	 * Climb method for simulated annealing
	 *
	 * @param map A given world map
	 * @param sequences Where to store the progressed sequences
	 * 
	 * @return Highest evaluation point
	 */
	public static Point3D simAnnealHillClimb(Map3D map, Vector<Point3D> sequence, ISchedule schedule) throws Exception
	{
		/** current pont */
		Point3D current = null;
		
		/** storage for potential successors */
		Point3D next = null; 
		
		/** temperature */
		float T = 0.0f;
		
		/** difference of evalFunction between current and difference */
		float deltaE = 0.0f;
		
		/** random numbers generator */
		Random randomGen = new Random();

		/** keep track of sequences */
		if (sequence == null) {
			sequence = new Vector<Point3D>();
		} else {
			sequence.clear();
		}
		
		/** set current to a random start point */
		current = map.get(randomGen.nextInt(map.getSize()));

		/** add to sequence */
		sequence.addElement(current);

		/** timer */
		MyTimer timer = new MyTimer();

		/** get it running */
		timer.start();
		
		/** for t <- 1 to infinity do */
		while (true) {
			
			/** T <- schedule[t] */
			T = schedule.eval(timer.getDuration());
			
			/** if T = 0 then return current */
			if (T == 0.0f) {
				/** in the end trim sequence to size */
				sequence.trimToSize();
				/** and return result */
				return current;
			}
			
			/** next <- a randomly selected successor of current */
			Vector<Point3D> neighbors = current.getNeighbors();
			next = neighbors.get(randomGen.nextInt(neighbors.size()));
			
			/** deltaE <- VALUE[next] - VALUE[current] */
			deltaE = next.getZ() - current.getZ();
			
			/** if deltaE > 0 then current <- next */
			if (deltaE > 0.0f) {
				current = next;
				sequence.addElement(current);
			} else {
				/** current <- next only with probability e^(deltaE / T) */
				
				/**
				 * get random number in [0.0f, 1.0f]
				 * fire, if number is in [0.0f, probability] with probability = Math.exp(deltaE / T)
				 */
				if (Math.random() <= Math.exp(deltaE / T)) {
					current = next;
					sequence.addElement(current);
				}		
				
			}  // else
			
		} // while
		
	} // simAnnealHillClimb(Map3D map, Vector<Point3D> sequence) throws Exception
	
} // class SimulatedAnnealing














